package project3;

import java.util.*;

public class Algorithms {

	public static void kmp(String inputString, String pattern) {
		int n = inputString.length();
		int m = pattern.length(); 
		inputString = "$" + inputString; //filler value
		pattern = "$" + pattern; //filler value
		int i = 1;
		int j = 1;
		List<Integer> borders = getBorderArray(pattern);
		List<Integer> results = new ArrayList<Integer>();
		
		while(i <= (n-m+j)) {
			while(j <= m && inputString.charAt(i) == pattern.charAt(j)) {
				i++;
				j++;
			}
			if(j == m+1) {
				results.add((i-m));
			}
			if(j == 1)
				i++;
			else
				j = borders.get(j);
		}
		System.out.println(results);
	}
	
	public static List<Integer> getBorderArray(String inputString) {
		List<Integer> borderArray = new ArrayList<Integer>();
		
		int n = inputString.length();
		int i = 0;
		int j = -1;
		
		borderArray.add(j); //b[0] = 0
		
		while(i < n) {
			while(j>=0 && inputString.charAt(i)!=inputString.charAt(j))
				j = borderArray.get(j);
			i++; j++;
			borderArray.add(i, j);
		}
		
		List<Integer> borders = new ArrayList<Integer>();
		
		borders.add(0,-1); //filler value for b[0]
		for(int a : borderArray) {
			borders.add(a+1);
		}		
		return borders;
	}
	
	public static void bm(String inputString, String pattern) {
		int n = inputString.length(); //filler value
		int m = pattern.length(); //filler value
		//Preprocess
		makeDeltaOne(pattern);
		makeDeltaTwoPartOne(inputString, pattern);
		makeDeltaTwoPartTwo(inputString, pattern);
		List<Integer> results = new ArrayList<Integer>();
				
		//Search
		int i = 0, j;
		while(i <= n-m) {
			j = m-1;
			while(j >= 0 && pattern.charAt(j) == inputString.charAt(i+j)) {
				j--;
			}
			if(j<0) {
				results.add(i+1);
				i += shiftDist.get(0);
			} else {
				i += Math.max(get(shiftDist, (j+1)), (j - get(deltaOne, inputString.charAt(i+j))));
			}
		}
		System.out.println(results.toString());
	}
	
	private static int get(HashMap<Integer, Integer> map, int key) {
		if(map.get(key) == null) {
			return 0;
		} else {
			return map.get(key);
		}
	}
	
	public static void makeDeltaTwoPartOne(String inputString, String pattern) {
		int i = pattern.length();
		int j = pattern.length()+1;
		deltaTwo = new HashMap<Integer,Integer>();
		shiftDist = new HashMap<Integer,Integer>();
		deltaTwo.put(i,j); // d[i]=j
		while(i > 0) {
			while(j <= pattern.length() && pattern.charAt(i-1) != pattern.charAt(j-1)) {
				if(shiftDist.get(j)== null) {
					shiftDist.put(j, j-i);
				}
				j = deltaTwo.get(j);
			}
			i--;
			j--;
			deltaTwo.put(i, j);
		}
	}
	
	public static void makeDeltaTwoPartTwo(String inputString, String pattern) {
		int i, j;
		j = deltaTwo.get(0);
		for(i=0; i<=pattern.length(); i++) {
			if(shiftDist.get(i) == null) {
				shiftDist.put(i, j);
			}
			if(i==j) {
				deltaTwo.put(j, j);
			}
		}
	}
	
	public static void makeDeltaOne(String pattern) {
		deltaOne = new HashMap<Integer, Integer>();
		for(int i = pattern.length()-1; i >= 0; i--) {
			if(deltaOne.get(pattern.charAt(i)) == null) {
				deltaOne.put((int) pattern.charAt(i), i);
			}
		}
	}
	
	static HashMap<Integer,Integer> deltaOne;
	static HashMap<Integer,Integer> deltaTwo;
	static HashMap<Integer,Integer> shiftDist;
}
